Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

The Hausdorff Distance

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their Hausdorff distance is \[ \vec{d}_H(X,Y)=\min\bigg\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\bigg\}. \]

Definition 2 (Hausdorff Distance) \[ d_H(X,Y)=\max\bigg\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\bigg\}. \]

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(X, Y\subset\) compact subsets. \[ \vec{d}^Z_H(X,Y)=\min\{r\geq0\mid X\subset \cup_{y\in Y} B(y,r)\}. \]

\[ d^Z_H(X,Y)=\max\bigg\{\vec{d}^Z_H(X,Y),\vec{d}^Z_H(Y,X)\bigg\}. \]

If \(Y=Z\), then \(d^Z_H(X,Z)=\vec{d}_H(Z,X)\).

\(S^1\) is the circle with circumference \(2\pi\)

\[ d_H(X,S^1)=\frac{\pi}{4}. \]

The Gromov–Hausdorff Distance

What if the subsets \(X,Y\) have no common embeddding?

Isometric embedding

\[ d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y)) \]

Some Properties and Results

  • \(d_{GH}(X,Y)=0\) if and only if \(X\), \(Y\) are isometric

  • \[\tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}\]

  • When \(X, Y\) are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If \(X,Y\) metric graphs, then \(NP\)-hard (A. Aggarawal et al.)

  • If \(X,Y\subset\mathbb{R}^1\), then \(\frac{5}{4}\)-approximable (Majhi et al.)

Hausdorff vs Gromov–Hausdorff

  • Let \((Z,d)\) be a metric space and \(X\subset Z\)
    • \(d^Z_H(X,Z)\) is well-defined
  • \((X,d)\) is also a metric space
    • \(d_{GH}(X,Z)\) can be defined

How the two distances \(d_{GH}(X,Z)\) and \(d^Z_H(X,Z)\) compare?

  • \(d_{GH}(X,Z)\leq d^Z_H(X,Z)\)

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{2} \]

\[ \frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2} \]

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{4} \]

\[ \frac{1}{2}0\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies ? \]

\(d_{GH}(X,S^1)=d_H(X,S^1)\)

Comparison on the Circle

\[ d_{GH}(X,S^1)<d_{H}(X,S^1)=\frac{\pi}{3}. \]

Goal

  • Our goal is to find lower bounds in terms of the Hausdorff distance.

  • The natural intuition is when a sample becomes dense enough, it starts to capture the geometry of the space.

Need pictures here.

Non-Trivial Lower Bounds

  • Bad News

For any \(\varepsilon>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < \varepsilon \cdot d_{H}(X,Z).\)

Closed Riemannian Manifolds

The Curious Case of the Circle

Theorem 1 (2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{6}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • The constant \(\frac{\pi}{3}\) is, indeed, optimal.

  • Picture here.

Theorem 3 (Two Subsets of the Cirlce) For \(X,Y\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)\geq d_H(X,S^1)\).

Metric Graphs

Questions

Thank you